package leetcode;

/**
 * @author caifangyi
 * @date 2022/8/8
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 1408. 数组中的字符串匹配
 *
 * 给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
 *
 * 如果你可以删除 words[j]最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
 *
 * 
 *
 * 示例 1：
 *
 * 输入：words = ["mass","as","hero","superhero"]
 * 输出：["as","hero"]
 * 解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
 * ["hero","as"] 也是有效的答案。
 * 示例 2：
 *
 * 输入：words = ["leetcode","et","code"]
 * 输出：["et","code"]
 * 解释："et" 和 "code" 都是 "leetcode" 的子字符串。
 * 示例 3：
 *
 * 输入：words = ["blue","green","bu"]
 * 输出：[]
 * 
 *
 * 提示：
 *
 * 1 <= words.length <= 100
 * 1 <= words[i].length <= 30
 * words[i] 仅包含小写英文字母。
 * 题目数据 保证 每个 words[i] 都是独一无二的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/string-matching-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Day1408 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String arr1[] = {"mass","as","hero","superhero"};
        List<String> strings1 = solution.stringMatching(arr1);
        System.out.println(strings1.stream().collect(Collectors.joining(",")));
        String arr2[] = {"leetcoder","leetcode","od","hamlet","am"};
        List<String> strings2 = solution.stringMatching(arr2);
        System.out.println(strings2.stream().collect(Collectors.joining(",")));
    }

    static class Solution {
        public List<String> stringMatching(String[] words) {
            Set<String> set = new HashSet<>();
            for (int i = 0; i < words.length-1; i++) {
                for (int j = i+1; j < words.length; j++) {
                    String word = match(words[i], words[j]);
                    if(word!=null){
                        set.add(word);
                    }
                }
            }
            return set.stream().toList();
        }

        private String match(String word1, String word2) {
            if(word1.length() > word2.length()){
                String temp = word1;
                word1 = word2;
                word2 = temp;
            }
            int i = word2.indexOf(word1);
            return i>=0?word1:null;
        }
    }
}
